An upper bound is an estimate, heuristic or calculated value that you know lies at or above the largest possible value of an unknown value or function. For example, before you roll a pair of dice, you know that the upper bound of the sum of the dice scores will be 36 (both dice show six dots). Knowing an upper bound can sometimes allow whole branches of a search tree or similar structure to be pruned. For example, if you are looking for the largest value in a tree and have found a node with value 7, and then consider an alterantive branch in the tree where a heuristic says the upper bound of all items below is 5, you can safely ignore the whole sub-tree.
. the opposite of an upper bound is a lower bound.
Used on page 115